Multiprocessors, which herein include multi-core processors, are becoming more widespread in the computer industry. As such, parallel execution of code in the multiprocessors is an important technique to take advantage of for performance gains. To optimize performance on multiprocessors, software programs need to be parallelized to take full advantage of parallel execution.
Generally, loops in a software program take additional time in the execution of a program. A technique to reduce this time is loop transformation. Loop transformations are used to increase the parallelism of the software program in modern compilers. Currently, there are many kinds of loop transformations, such as fusion, fission, blocking, shifting, GCD (greatest common divisor) transformation, unimodular transformation, and affine partitioning.
Loop shifting, in particular, involves moving operations from one iteration of the loop body to a different iteration of the loop body. It does this by shifting a set of operations from the beginning of the loop body to the end of the loop body. A copy of these operations is also placed in the loop head or prologue. Loop shifting shifts a set of operations one at a time, thereby exposing just as much parallelism as can be exploited by the available resources. Parallelizing transformations can then operate on the shifted operations to further compact the loop body. Loop shifting can be a beneficial technique to expose parallelism in order to increase the performance, area, and resource utilization of a multiprocessor.